Hand of straights

Time: O(NLogN); Space: O(N); medium

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return True if and only if she can.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3

Output: True

Explanation:

  • Alice’s hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4

Output: False

Explanation:

  • Alice’s hand can’t be rearranged into groups of 4.

Constraints:

  • 1 <= len(hand) <= 10000

  • 0 <= hand[i] <= 10^9

  • 1 <= W <= len(hand)

Note:

  • This question is the same as 1296

1. Heap [O(NLogN), O(N)]

[14]:

from collections import Counter
from heapq import heapify, heappop

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def isNStraightHand(self, hand, W):
        """
        :type hand: List[int]
        :type W: int
        :rtype: bool
        """
        if len(hand) % W:
            return False

        counts = Counter(hand)
        min_heap = list(hand)
        heapify(min_heap)

        for _ in range(len(min_heap)//W):
            while counts[min_heap[0]] == 0:
                heappop(min_heap)
            start = heappop(min_heap)
            for _ in range(W):
                counts[start] -= 1
                if counts[start] < 0:
                    return False
                start += 1

        return True

[15]:

s = Solution1()

hand = [1,2,3,6,2,3,4,7,8]
W = 3
assert s.isNStraightHand(hand, W) == True

hand = [1,2,3,4,5]
W = 4
assert s.isNStraightHand(hand, W) == False

2. Brute Force [O(N x (N / W)), O(N)]

Intuition

We will repeatedly try to form a group (of size W) starting with the lowest card. This works because the lowest card still in our hand must be the bottom end of a size W straight.

Algorithm

Let’s keep a count {card: number of copies of card} as a TreeMap (or dict).

Then, repeatedly we will do the following steps: find the lowest value card that has 1 or more copies (say with value x), and try to remove x, x+1, x+2, …, x+W-1 from our count. If we can’t, then the task is impossible.

[16]:

import collections

class Solution2(object):
    """
    Time: O(N∗(N/W)), where N is the length of hand.
          The (N/W) factor comes from min(count).
          Note: In Java, the (N/W) factor becomes LogN due to the complexity of TreeMap.
    Space: O(N).
    """
    def isNStraightHand(self, hand, W):
        """
        :type hand: List[int]
        :type W: int
        :rtype: bool
        """
        count = collections.Counter(hand)

        while count:
            m = min(count)
            for k in range(m, m+W):
                v = count[k]
                if not v: return False
                if v == 1:
                    del count[k]
                else:
                    count[k] = v - 1

        return True

[17]:

s = Solution2()

hand = [1,2,3,6,2,3,4,7,8]
W = 3
assert s.isNStraightHand(hand, W) == True

hand = [1,2,3,4,5]
W = 4
assert s.isNStraightHand(hand, W) == False

Get straight hands

[18]:

import heapq

class Solution1(object):
    """
    Time: O(N*LogN*W)
    Space: O(N)
    """
    def straightHands(self, hand, W):

        pq = []
        for num in hand:
            heapq.heappush(pq, num)
        straights = []

        while len(pq) > 0:
            straight = []
            dumps = []

            while len(pq) > 0 and len(straight) < W:
                pop = heapq.heappop(pq)
                if len(straight) == 0 or pop == straight[-1] + 1:
                    straight.append(pop)
                else:
                    dumps.append(pop)
            straights.append(straight)

            if len(straight) < W:
                return []
            else:
                for dump in dumps:
                    heapq.heappush(pq, dump)

        return straights

[19]:

s = Solution1()

hand = [1,2,3,6,2,3,4,7,8]
W = 3
# print(s.straightHands(hand, W))
assert s.straightHands(hand, W) == [[1, 2, 3], [2, 3, 4], [6, 7, 8]]

hand = [1,2,3,4,5]
W = 4
# print(s.straightHands(hand, W))
assert s.straightHands(hand, W) == []